package algorithm.leetcode;

import java.util.Arrays;

/**
 * @author wuwen
 * @since 2023/12/20
 */
public class NO31_下一个排列 {
    public static void main(String[] args) {
        int[] handles = new int[]{4, 2, 0, 2, 3, 2, 0};
        new Solution().nextPermutation(handles);
        System.out.println("handles = " + Arrays.toString(handles));
    }

    static class Solution {
        public void nextPermutation(int[] primitives) {
            int i, j;
            int size = primitives.length;
            for (i = size - 1; i >= 0; i--) {
                for (j = size - 1; j > i; j--) {
                    if (primitives[i] < primitives[j]) {
                        swap(primitives, i, j);
                        reverseArray(primitives, i + 1, size);
                        return;
                    }
                }
            }
            reverseArray(primitives);
        }

        private void swap(int[] array, int i, int j) {
            if (i == j) {
                return;
            }
            array[i] ^= array[j];
            array[j] ^= array[i];
            array[i] ^= array[j];
        }

        private void reverseArray(int[] array, int i, int j) {
            j--;
            while (i < j) {
                swap(array, i++, j++);
            }
        }

        private void reverseArray(int[] array) {
            reverseArray(array, 0, array.length);
        }
    }
}
